package com.dylan.历史.算法;

/**
 * Created by Dylan on 2018/8/1.
 *
 * 给定一个字符串str，返回str的最长无重复字符串的长度.
 * 例："abcd"是4，"aabcb"，最长无重复字符串为"abc"，返回3.
 */
public class 无重复字符串 {

    public static void main(String[] args) {
        System.out.println(maxUnique("aabcb"));
    }


    public static int maxUnique(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chars = str.toCharArray();
        // 哈希表,key表示某个字符,value表示这个字符最近一次出现的位置.
        int[] map = new int[256];
        for (int i = 0; i < map.length; i++) {
            map[i] = -1;
        }
        int cur = 0; // 当前计算出的不重复字符串最大长度
        int pre = -1; // 当前计算出的不重复字符串开始位置的前一个位置
        int len = 0; // 最长不重复字符串的长度
        for (int i = 0; i != chars.length; i++) {
            // 如果当前字符之前出现过,则将当前字符之前出现的位置作为新的不重复字符串开始位置的前一个位置
            pre = Math.max(pre, map[chars[i]]);
            // 新的不重复字符串的长度
            cur = i - pre;
            // 取最大值
            len = Math.max(len, cur);
            // 将当前字符的位置保存到哈希表中
            map[chars[i]] = i;
        }
        return len;
    }
}
